#!/usr/local/bin/omf

# implicit main
include "inc/lists/takeskip.inc";

# expects $1 type LIST (of all INT for now)
function mergesort {
	if $1 == []
	    return [];
	if tl($1) == []
	    return $1;
	return merge(mergesort(take($1)), mergesort(skip($1)));
}

# expects both $1 and $2 type LIST
function merge {
	if $1 == []
	    return $2;
	if $2 == []
	    return $1;

	var x = hd($1);
	var y = hd($2);
	if x < y
	    return x::merge(tl($1), $2);
	return y::merge($1, tl($2));
}
